#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include "map.h"



// 默认哈希函数（整数或指针）
static unsigned long default_hash_func(const void *key) {
    return (unsigned long)key;
}

// 默认键比较函数
static int default_key_compare(const void *srcKey, const void *destKey) {
    return srcKey == destKey;
}

// 创建哈希表
HashMap* hashmap_create(
    size_t capacity,
    size_t keySize,
    size_t valueSize,
    unsigned long (*hash_func)(const void *),
    int (*key_compare)(const void *, const void *),
    void (*key_free)(void *),
    void (*value_free)(void *)
) {
    HashMap *map = malloc(sizeof(HashMap));
    if (!map) return NULL;
    
    // 初始容量调整为最接近的2的幂
    size_t initCapacity = 8;
    while (initCapacity < capacity) initCapacity <<= 1;
    
    map->buckets = calloc(initCapacity, sizeof(kvPair *));
    if (!map->buckets) {
        free(map);
        return NULL;
    }
    map->capacity = capacity;
    map->size = 0;
    map->keySize = keySize;
    map->valueSize = valueSize;
    map->hash_func = hash_func ? hash_func : default_hash_func;
    map->key_compare = key_compare ? key_compare : default_key_compare;
    map->key_free = key_free;
    map->value_free = value_free;
    return map;
}

// 释放节点内存
static void free_keyValue(HashMap *map, kvPair *kv) {
    if (map->key_free) map->key_free(kv->key);
    if (map->value_free) map->value_free(kv->value);
    free(kv);
}



// 扩容哈希表
static void resize_hashmap(HashMap *map, size_t new_capacity) {
    kvPair **new_buckets = calloc(new_capacity, sizeof(kvPair *));
    if (!new_buckets) return;
    
    // 重新插入所有元素
    for (size_t i = 0; i < map->capacity; i++) {
        kvPair *current = map->buckets[i];
        while (current) {
            kvPair *next = current->next;
            
            // 计算新位置
            
            size_t new_index = map->hash_func(current->key) & (new_capacity - 1);
            
            // 插入新桶
            current->next = new_buckets[new_index];
            new_buckets[new_index] = current;
            
            current = next;
        }
    }
    
    free(map->buckets);
    map->buckets = new_buckets;
    map->capacity = new_capacity;
}

// 插入键值对
int hashmap_put(HashMap *map, const void *key, const void *value) {
    if (!map || !key) return 0;
    
    // 检查是否需要扩容（负载因子 > 0.75）
    if (map->size >= map->capacity * 0.75) {
        resize_hashmap(map, map->capacity << 1);
    }
    
    size_t index = map->hash_func(key) & (map->capacity - 1);
    kvPair *current = map->buckets[index];
    
    // 检查键是否已存在
    while (current) {
        if (map->key_compare(current->key, key)) {
            // 更新值
            if (map->value_free) map->value_free(current->value);
            if (map->valueSize > 0) {
                memcpy(current->value, value, map->valueSize);
            } else {
                current->value = (void *)value;
            }
            return 1;
        }
        current = current->next;
    }
    
    // 创建新节点
    kvPair *new_kv = malloc(sizeof(kvPair));
    if (!new_kv) return 0;
    
    // 分配键内存
    if (map->keySize > 0) {
        new_kv->key = malloc(map->keySize);
        memcpy(new_kv->key, key, map->keySize);
    } else {
        new_kv->key = (void *)key;
    }
    
    // 分配值内存
    if (map->valueSize > 0) {
        new_kv->value = malloc(map->valueSize);
        memcpy(new_kv->value, value, map->valueSize);
    } else {
        new_kv->value = (void *)value;
    }
    
    // 插入链表头部
    new_kv->next = map->buckets[index];
    map->buckets[index] = new_kv;
    map->size++;
    return 1;
}

// 查找键
void* hashmap_get(HashMap *map, const void *key) {
    if (!map || !key) return NULL;
    
    size_t index = map->hash_func(key) & (map->capacity - 1);
    kvPair *current = map->buckets[index];
    
    while (current) {
        if (map->key_compare(current->key, key)) {
            return current->value;
        }
        current = current->next;
    }
    
    return NULL;
}

// 删除键
int hashmap_remove(HashMap *map, const void *key, free_kvPair free_kv) {
    if (!map || !key) return 0;
    
    size_t index = map->hash_func(key) & (map->capacity - 1);
    kvPair *current = map->buckets[index];
    kvPair *prev = NULL;
    
    while (current) {
        if (map->key_compare(current->key, key)) {
            if (prev) {
                prev->next = current->next;
            } else {
                map->buckets[index] = current->next;
            }
            free_kv(map, current);
            map->size--;
            return 1;
        }
        
        prev = current;
        current = current->next;
    }
    
    return 0;
}

// 销毁哈希表
void hashmap_destroy(HashMap *map) {
    if (!map) return;
    
    for (size_t i = 0; i < map->capacity; i++) {
        kvPair *current = map->buckets[i];
        while (current) {
            kvPair *next = current->next;
            free_keyValue(map, current);
            current = next;
        }
    }
    
    free(map->buckets);
    free(map);
}


// 整数哈希函数
unsigned long int_hash(const void *key) {
    long k = *(long *)key;
    k = ((k >> 16) ^ k) * 0x45d9f3b;
    k = ((k >> 16) ^ k) * 0x45d9f3b;
    return (unsigned long)((k >> 16) ^ k);
}

// 整数键比较
int int_compare(const void *srcKey, const void *destKey) {
    return *(int *)srcKey == *(int *)destKey;
}

// 字符串哈希函数 (djb2)
unsigned long string_hash(const void *key) {
    const char *str = (const char *)key;
    unsigned long hash = 5381;
    int c;
    while ((c = *str++)) {
        hash = ((hash << 5) + hash) + (unsigned long)c; /* hash * 33 + c */
    }
    return hash;
}

// 字符串比较
int string_compare(const void *srcKey, const void *destKey) {
    return strcmp((const char *)srcKey, (const char *)destKey) == 0;
}


/*---------- 队列操作 ----------*/

typedef struct QueueNode {                
    Any   data;                      
    struct QueueNode* next;
} QueueNode;

typedef struct {
    QueueNode* front;
    QueueNode* rear;
    int count;              // 队列元素计数
} Queue;

// 创建队列
Queue* createQueue() {
    Queue* q = (Queue*)malloc(sizeof(Queue));
    q->front = q->rear = NULL;
    q->count = 0;
    return q;
}

// 入队
void enqueue(Queue* q, Any data) {
    QueueNode* newNode = (QueueNode*)malloc(sizeof(QueueNode));
    newNode->data = data;
    newNode->next = NULL;

    if (q->rear) {
        q->rear->next = newNode;
        q->rear = newNode;
    } else {
        q->front = q->rear = newNode;
    }
    q->count++;
}
// 出队
Any dequeue(Queue* q) {
    if (!q->front) return NULL;

    QueueNode* temp = q->front;
    Any data = temp->data;

    q->front = q->front->next;
    if (!q->front) q->rear = NULL;
    
    free(temp);
    q->count--;
    return data;
}
// 队列是否为空
int isEmpty(Queue* q) {
    return q->count == 0;
}

// hashmap添加topo节点
int hashmap_add_topo_node(HashMap* graph, const void* key, Any data) {
    TopoNode* node = (TopoNode*)malloc(sizeof(TopoNode));
    node->data = data;
    node->indegree = 0;
    node->adj = NULL;
    return hashmap_put(graph, key, node);
}

// hashmap建立依赖关系
int hashmap_add_topo_dependence(HashMap* graph, const void*  srcKey, const void* destKey) {
    TopoNode* srcNode = hashmap_get(graph, srcKey); 
    TopoNode* destNode = hashmap_get(graph, destKey);
    if ( !srcNode || !destNode || !srcNode->data || !destNode->data) 
    {
        return 0;
    }
    AdjTable* newAdj = (AdjTable*)malloc(sizeof(AdjTable));
    newAdj->dest = (void*)destKey;
    newAdj->next = srcNode->adj;
    srcNode->adj = newAdj;
    destNode->indegree++;
    return 1;
}

// 计算拓扑排序
int hashmap_topo_sort(HashMap* graph, TopoSortResult* result) {
    if (graph->size == 0) return -1;

    Queue* queue = createQueue();
    Any* order = (Any*)malloc(graph->size * sizeof(Any));
    int* batches = (int*)malloc(graph->size * sizeof(int));
    size_t count = 0;
    int currentBatch = 0;

    // 初始化队列
    for (size_t i = 0; i < graph->capacity; i++) {
        kvPair* current = graph->buckets[i];
        while (current) {
            TopoNode* node = (TopoNode*)current->value;
            if (node->data&&node->indegree == 0) {
                enqueue(queue, current->key);
            }
            current = current->next;
        }
    }
    // 入队   
    while (!isEmpty(queue)) {
        int levelSize = queue->count;
        for (int i = 0; i < levelSize; i++) {
            Any k = dequeue(queue);
            TopoNode* node = (TopoNode*)hashmap_get(graph, k);
            order[count] = node->data;
            batches[count]=currentBatch;
            count++;
            // 减少入度
            if (!node) continue;
            // 更新邻接节点入度
            AdjTable* adj = node->adj;
            while (adj) {
                TopoNode* adjNode = hashmap_get(graph, adj->dest);
                if (adjNode && --adjNode->indegree == 0) {
                    enqueue(queue, adj->dest);
                }   
                adj = adj->next;
            }
            
        }
        currentBatch++;
    }
    // printf("count:%ld\n",count);
    if (count == graph->size)
    {
        result->order = order;
        result->batches = batches;
        result->size = count;
        result->totalBatches = currentBatch;
    }else {
        free(order);
        free(batches);
    }
    
    free(queue);
    return 0;
}
